package com.ljy.my_study.leetcode.单词接龙;

import java.util.*;

/** 
* @author James
* @date 2018年9月27日 
*/
public class TestMain {
//	给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
//
//	每次转换只能改变一个字母。
//	转换过程中的中间单词必须是字典中的单词。
//	说明:
//
//	如果不存在这样的转换序列，返回 0。
//	所有单词具有相同的长度。
//	所有单词只由小写字母组成。
//	字典中不存在重复的单词。
//	你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
//	示例 1:
//
//	输入:
//	beginWord = "hit",
//	endWord = "cog",
//	wordList = ["hot","dot","dog","lot","log","cog"]
//
//	输出: 5
//
//	解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
//	     返回它的长度 5。
//	示例 2:
//
//	输入:
//	beginWord = "hit"
//	endWord = "cog"
//	wordList = ["hot","dot","dog","lot","log"]
//
//	输出: 0
//
//	解释: endWord "cog" 不在字典中，所以无法进行转换。
	public static void main(String[] args) {
		String[] words= {"hot","dot","dog","lot","log","cog"};
		System.out.println(ladderLength2("hit","cog",Arrays.asList(words)));
		words=
			new String[]{"kid","tag","pup","ail","tun","woo","erg","luz","brr","gay","sip","kay","per","val","mes","ohs",
				"now","boa","cet","pal","bar","die","war","hay","eco","pub","lob","rue","fry","lit","rex","jan","cot","bid","ali","pay","col","gum","ger","row","won","dan","rum","fad","tut","sag","yip","sui","ark","has","zip","fez","own","ump","dis","ads","max","jaw","out","btu","ana","gap","cry","led","abe","box","ore","pig","fie","toy","fat","cal","lie","noh","sew","ono","tam","flu","mgm","ply","awe","pry","tit","tie","yet","too","tax","jim","san","pan","map","ski","ova","wed","non","wac","nut","why","bye","lye","oct","old","fin","feb","chi","sap","owl","log","tod","dot","bow","fob","for","joe","ivy","fan","age","fax","hip","jib","mel","hus","sob","ifs","tab","ara","dab","jag","jar","arm","lot","tom","sax","tex","yum","pei","wen","wry","ire","irk","far","mew","wit","doe","gas","rte","ian","pot","ask","wag","hag","amy","nag","ron","soy","gin","don","tug","fay","vic","boo","nam","ave","buy","sop","but","orb","fen","paw","his","sub","bob","yea","oft","inn","rod","yam","pew","web","hod","hun","gyp","wei","wis","rob","gad","pie","mon","dog","bib","rub","ere","dig","era","cat","fox","bee","mod","day","apr","vie","nev","jam","pam","new","aye","ani","and","ibm","yap","can","pyx","tar","kin","fog","hum","pip","cup","dye","lyx","jog","nun","par","wan","fey","bus","oak","bad","ats","set","qom","vat","eat","pus","rev","axe","ion","six","ila","lao","mom","mas","pro","few","opt","poe","art","ash","oar","cap","lop","may","shy","rid","bat","sum","rim","fee","bmw","sky","maj","hue","thy","ava","rap","den","fla","auk","cox","ibo","hey","saw","vim","sec","ltd","you","its","tat","dew","eva","tog","ram","let","see","zit","maw","nix","ate","gig","rep","owe","ind","hog","eve","sam","zoo","any","dow","cod","bed","vet","ham","sis","hex","via","fir","nod","mao","aug","mum","hoe","bah","hal","keg","hew","zed","tow","gog","ass","dem","who","bet","gos","son","ear","spy","kit","boy","due","sen","oaf","mix","hep","fur","ada","bin","nil","mia","ewe","hit","fix","sad","rib","eye","hop","haw","wax","mid","tad","ken","wad","rye","pap","bog","gut","ito","woe","our","ado","sin","mad","ray","hon","roy","dip","hen","iva","lug","asp","hui","yak","bay","poi","yep","bun","try","lad","elm","nat","wyo","gym","dug","toe","dee","wig","sly","rip","geo","cog","pas","zen","odd","nan","lay","pod","fit","hem","joy","bum","rio","yon","dec","leg","put","sue","dim","pet","yaw","nub","bit","bur","sid","sun","oil","red","doc","moe","caw","eel","dix","cub","end","gem","off","yew","hug","pop","tub","sgt","lid","pun","ton","sol","din","yup","jab","pea","bug","gag","mil","jig","hub","low","did","tin","get","gte","sox","lei","mig","fig","lon","use","ban","flo","nov","jut","bag","mir","sty","lap","two","ins","con","ant","net","tux","ode","stu","mug","cad","nap","gun","fop","tot","sow","sal","sic","ted","wot","del","imp","cob","way","ann","tan","mci","job","wet","ism","err","him","all","pad","hah","hie","aim","ike","jed","ego","mac","baa","min","com","ill","was","cab","ago","ina","big","ilk","gal","tap","duh","ola","ran","lab","top","gob","hot","ora","tia","kip","han","met","hut","she","sac","fed","goo","tee","ell","not","act","gil","rut","ala","ape","rig","cid","god","duo","lin","aid","gel","awl","lag","elf","liz","ref","aha","fib","oho","tho","her","nor","ace","adz","fun","ned","coo","win","tao","coy","van","man","pit","guy","foe","hid","mai","sup","jay","hob","mow","jot","are","pol","arc","lax","aft","alb","len","air","pug","pox","vow","got","meg","zoe","amp","ale","bud","gee","pin","dun","pat","ten","mob"};
		long start=System.currentTimeMillis();
//		System.out.println(ladderLength("cet","ism",Arrays.asList(words)));
//		System.out.println(System.currentTimeMillis()-start);
//		start=System.currentTimeMillis();
		System.out.println(ladderLength2("cet","ism",Arrays.asList(words)));
		System.out.println(System.currentTimeMillis()-start);

	}

	public static int ladderLength2(String beginWord, String endWord, List<String> wordList) {
		int count=Integer.MAX_VALUE;
		Queue<Set<Integer>> queue=new LinkedList<>();
		Set<Integer> startSet= new LinkedHashSet<>();
		startSet.add(-1);
		queue.offer(startSet);
		Queue<Integer> lastIndexQueue=new LinkedList<>();
		lastIndexQueue.offer(-1);
		do{
			Set<Integer> nextSet=queue.poll();
			Integer lastIndex=lastIndexQueue.poll();
			for(int i=0;i<wordList.size();i++){
				if(nextSet.contains(i)){
					continue;
				}
				String word;
				if(lastIndex==-1){
					word=beginWord;
				}else{
					word=wordList.get(lastIndex);
				}
				String nextWord=wordList.get(i);
				if(isSimilar(word,nextWord)){
					Set<Integer> newSet=new LinkedHashSet<>(nextSet);
					newSet.add(i);
					queue.offer(newSet);
					lastIndexQueue.offer(i);
					if(isSimilar(endWord,nextWord)){
						count=Math.min(count,nextSet.size()+2);
						print(wordList,nextSet,beginWord,endWord);
					}
				}
			}
		}while(!queue.isEmpty());
		if(count==Integer.MAX_VALUE){
			return 0;
		}
		return count;
	}

	private static void print(List<String> wordList,Set<Integer> set,String beginWord,String endWord){
		Iterator<Integer> it= set.iterator();
		while(it.hasNext()){
			Integer lastIndex=it.next();
			if(lastIndex==-1){
				System.out.print(beginWord+";");
			}else{
				System.out.print(wordList.get(lastIndex)+";");
			}
		}
		System.out.print(endWord+";");
		System.out.println();
	}

	public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
		if(!wordList.contains(endWord))return 0;
		Map<String,Integer> map=new HashMap<>();
		int len=wordList.size();
		List<List<String>> listList=new ArrayList<>();
		List<String> rootList=new ArrayList<>();
		rootList.add(beginWord);
		listList.add(rootList);
		map.put(beginWord, 1);
		int count=0;
		int start=0;
		int end=listList.size();
		while(count<len) {
			for(int i=start;i<end;i++) {
				List<String> sList=listList.get(i);
				String lOne=null;
				int size=sList.size();
				if(size>1)lOne=sList.get(size-2);
				String one=sList.get(size-1);
				for(String s:wordList) {
					if((lOne==null||(lOne!=null&&!lOne.equals(s)))
							&&isSimilar(one,s)) {
						List<String> l=new ArrayList<>(sList);
						l.add(s);
						listList.add(l);
						map.put(s, 1);
						if(s.equals(endWord)) {
							System.out.println(l);
							return size+1;
						}
					}
				}
			}
			count++;
			start=end;
			end=listList.size();
		}
        return 0;
    }
	
	private static boolean isSimilar(String a,String b) {
		byte count=0;
		char[] aArr=a.toCharArray();
		char[] bArr=b.toCharArray();
		for(int i=0;i<aArr.length;i++) {
			if(aArr[i]==bArr[i]) {
				count++;
			}
		}
		if(count==aArr.length-1) 
			return true;
		else 
			return false;
	}
}
